#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"

void MergeSort(int* a, int n)
{
	int* buf = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0,n-1, buf);
	free(buf);
}
void _MergeSort(int* a, int left,int right, int* buf)
{
	if (left >= right)
		return;
	int mid = (left + right) / 2;
	int left1 = left;
	int left2 = mid+1;
	int right1 = mid;
	int right2 = right;
	
	_MergeSort(a, left1, right1, buf);
	_MergeSort(a, left2, right2, buf);
	int i = left;
	while (left1 <= right1 && left2 <= right2)
	{
		if (a[left1] < a[left2])
		{
			buf[i] = a[left1];
			left1++;
		}
		else 
		{
			buf[i] = a[left2];
			left2++;
		}
		i++;
	}
	while (left1 <= right1)
	{
		buf[i] = a[left1];
		left1++;
		i++;
	}
	while (left2 <= right2)
	{
		buf[i] = a[left2];
		left2++;
		i++;
	}
	memcpy(a, buf, sizeof(int) * (right + 1));

}
